<?php
// 将结点抽象成一个node class，具备data和next两个属性
class Node{
    public $data = null;
    public $next = null;
    public function __construct( $data = null ){
        $this->data = $data;
    }
}
// 单链表的存储
class Linked_sq{
    private $head = null;
    public function __construct(){
        // 添加一个头结点
        $this->head = new Node();
    }
    /*
     * @desc : 获取单链表长度
     */
    public function get_length(){
        // 注意 头结点 不算在单链表的长度内
        $length = 0;
        $head = $this->head;
        while( $head->next ){
            $head = $head->next;
            $length++;
        }
        return $length;
    }
    /*
     * @desc : 添加一个结点
     * @param : index
     * @param : item
     */
    public function add_item( $index, $item ){
        $length = $this->get_length();
        if( $index < 0 || $index > $length ){
            return false;
        }
        // 获取头结点
        $head = $this->head;
        for( $i = 0; $i < $index; $i++){
            $head = $head->next;
        }
        // 初始化一个新结点
        $node = new Node( $item );
        $node->next = $head->next;
        $head->next = $node;
        return true;
    }
    /*
     * @desc : 删除一个结点
     * @param : index
     */
    public function delete_item( $index ){
        $length = $this->get_length();
        if( $index < 0 || $index > $length ){
            return null;
        }
        $head = $this->head;
        // 这里循环的终止条件一定要想明白了，我要删除index位置上的结点，从0开始寻找一直到index这个结点，但是
        // 当循环终止的时候，被选中的结点是 index - 1 位置上的结点
        for( $i = 0; $i < $index; $i++ ){
            $head = $head->next;
        }
        // 这个才是要被删除的结点
        $delete_node = $head->next;
        $value = $delete_node->data;
        // 修改指针指向
        $head->next = $head->next->next;
        // 删除结点
        unset( $delete_node );
        return $value;
    }
    /*
     * @desc : 查找某个位置上的数值
     * @param : index
     */
    public function get_item_by_index( $index ){
        $length = $this->get_length();
        if( $index < 0 || $index > $length ){
            return null;
        }
        $head = $this->head;
        // 注意这里终止条件，这里获取到的是 index-1 位置上的结点
        for( $i = 0; $i < $index; $i++ ){
            $head = $head->next;
        }
        return $head->next->data;
    }
    /*
     * @desc : 清空整个单链表
     */
    public function truncate(){
        // 第一个结点,就是头结点
        $head = $this->head;
        while( $head->next ){
            $temp = $head->next;
            unset( $head->next );
            $head = $temp;
        }
        return true;
    }
    /*
     * @desc : 栈的pop方法
     */
    public function pop(){
        $length = $this->get_length();
        return $this->delete_item( $length - 1 );
    }
    /*
     * @desc : 栈的push方法
     */
    public function push( $item ){
        $length = $this->get_length();
        $this->add_item( $length, $item );
    }
}

$link = new Linked_sq();
echo '单链表初始长度为：'.$link->get_length().PHP_EOL;
// 添加一个结点
$link->push( 9 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
$link->push( 1 );
$link->push( 2 );
$link->push( 5 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
echo '第二个位置上的：'.$link->get_item_by_index( 1 ).PHP_EOL;
$link->pop();
echo '单链表长度为：'.$link->get_length().PHP_EOL;